﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<set>
#include<map>
using namespace std;

void test01()
{
	// 去重+升序排序
	set<int> s;
	// 去重+降序排序（给一个大于的仿函数）
	//set<int, greater<int>> s;
	s.insert(5);
	s.insert(2);
	s.insert(7);
	s.insert(5);
	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{// error C3892: “it”: 不能给常量赋值
	 // *it = 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 插如一段initializer_list列表值，已经存在的值插如失败
	s.insert({ 2,8,3,9 });
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	set<string> strset = { "sort", "insert", "add" };
	// 遍历string比较ascll码大小顺序遍历的
	for (auto& e : strset)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test02()
{
	set<int> s = { 4,2,7,2,8,5,9 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 删除最小值
	s.erase(s.begin());
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	// 直接删除x

	int x;
	cin >> x;
	int num = s.erase(x);
	if (num == 0)
	{
		cout << x << "不存在！" << endl;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 直接查找再利用迭代器删除x
	cin >> x;
	auto pos = s.find(x);
	if (pos != s.end())
	{
		s.erase(pos);
	}
	else
	{
		cout << x << "不存在！" << endl;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 算法库的查找 O(N)
	auto pos1 = find(s.begin(), s.end(), x);
	// set自身实现的查找 O(logN)
	auto pos2 = s.find(x);
	// 利⽤count间接实现快速查找
	cin >> x;
	if (s.count(x))
	{
		cout << x << "在！" << endl;
	}
	else
	{
		cout << x << "不存在！" << endl;
	}
}

void test03()
{
	// 相比set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 相比set不同的是，x可能会存在多个，find查找中序的第一个
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	// 相比set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;
	// 相比set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

}

//class Solution {
//public:
//	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//		set<int> s1(nums1.begin(), nums1.end());
//		set<int> s2(nums2.begin(), nums2.end());
//		// 因为set遍历是有序的，有序值，依次⽐较
//		// ⼩的++，相等的就是交集
//		vector<int> ret;
//		auto it1 = s1.begin();
//		auto it2 = s2.begin();
//		while (it1 != s1.end() && it2 != s2.end())
//		{
//			if (*it1 < *it2)
//			{
//				it1++;
//			}
//			else if (*it1 > *it2)
//			{
//				it2++;
//			}
//			else
//			{
//				ret.push_back(*it1);
//				it1++;
//				it2++;
//			}
//		}
//		return ret;
//	}
//};

//class Solution {
//public:
//	ListNode* detectCycle(ListNode* head) {
//		set<ListNode*> s;
//		ListNode* cur = head;
//		while (cur)
//		{
//			auto ret = s.insert(cur);
//			if (ret.second == false)
//				return cur;
//			cur = cur->next;
//		}
//		return nullptr;
//	}
//};
// 
//typedef pair<const Key, T> value_type;

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;

	//默认构造
	pair() : first(T1()), second(T2())
	{}
	//构造
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
	//拷贝构造
	template<class U, class V>
	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
	{}
};

//template <class T1, class T2>
//inline pair<T1, T2> make_pair(T1 x, T2 y)
//{
//	return (pair<T1, T2>(x, y));
//}

//// empty (1) 无参默认构造
//explicit map(const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());
//// range (2) 迭代器区间构造
//template <class InputIterator>
//map(InputIterator first, InputIterator last,
//	const key_compare& comp = key_compare(),
//	const allocator_type & = allocator_type());
//// copy (3) 拷贝构造
//map(const map& x);
//// initializer list (5) initializer 列表构造
//map(initializer_list<value_type> il,
//	const key_compare& comp = key_compare(),
//	const allocator_type& alloc = allocator_type());
//// 迭代器是⼀个双向迭代器
//iterator->a bidirectional iterator to const value_type
//// 正向迭代器
//iterator begin();
//iterator end();
//// 反向迭代器
//reverse_iterator rbegin();
//reverse_iterator rend();

//int main()
//{
//	std::set<int> myset;
//	for (int i = 1; i < 10; i++)
//		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	// 实现查找到的[itlow,itup)包含[30, 60]区间
//	// 返回 >= 30
//	auto itlow = myset.lower_bound(30);
//	// 返回 > 60，位置是指向60后面
//	auto itup = myset.upper_bound(60);
//	// 删除这段区间的值
//	myset.erase(itlow, itup);
//	for (auto e : myset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

void test04()
{
	map<string, string> dict = { {"pizza","披萨"},{"lemon","柠檬"},{"tea","茶"} };
	auto it = dict.begin();
	/*while (it != dict.end())
	{
		cout << it->first << " : " << it->second << endl;
		++it;
	}*/
	/*for (auto [k, v] : dict)
	{
		cout << k << ":" << v << endl;
	}
	cout << endl;*/
	for (const auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	for (const auto& [k,v] : dict)
	{
		cout << k << ":" << v << endl;
	}
}

void test05()
{
	map<string, string> dict = { {"pizza","披萨"},{"lemon","柠檬"},{"tea","茶"} };

	//key不存在->插入{"OREO",string()}
	dict["OREO"];

	//key不存在->插入+修改
	dict["computer"] = "电脑";

	//key存在->查找
	cout << dict["pizza"] << endl;

	//key存在->修改
	dict["OREO"] = "奥利奥";
}

void test06()
{
	string arr[] = { "披萨" ,"柠檬","茶","披萨" ,"披萨" ,"茶",
		"披萨","柠檬" ,"披萨","茶" };
	map<string, int> count;
	for (auto& str : arr)
	{
		count[str]++;
	}
	for (const auto& e : count)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

//class Solution {
//public:
//	Node* copyRandomList(Node* head) {
//		map<Node*, Node*> nodeMap;
//		Node* copyhead = nullptr, * copytail = nullptr;
//		Node* cur = head;
//		while (cur)
//		{
//			if (copytail == nullptr)
//			{
//				copyhead = copytail = new Node(cur->val);
//			}
//			else
//			{
//				copytail->next = new Node(cur->val);
//				copytail = copytail->next;
//			}
//			// 原节点和拷⻉节点map kv存储
//			nodeMap[cur] = copytail;
//			cur = cur->next;
//		}
//		// 处理random
//		cur = head;
//		Node* copy = copyhead;
//		while (cur)
//		{
//			if (cur->random == nullptr)
//			{
//				copy->random = nullptr;
//			}
//			else
//			{
//				copy->random = nodeMap[cur->random];
//			}
//			cur = cur->next;
//			copy = copy->next;
//		}
//		return copyhead;
//	}
//};

//class Solution {
//public:
//	struct Compare
//	{
//		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
//			const
//		{
//			return x.second > y.second;
//		}
//	};
//	vector<string> topKFrequent(vector<string>& words, int k) {
//		map<string, int> countMap;
//		for (auto& e : words)
//		{
//			countMap[e]++;
//		}
//		vector<pair<string, int>> v(countMap.begin(), countMap.end());
//		// 仿函数控制降序
//		stable_sort(v.begin(), v.end(), Compare());
//		//sort(v.begin(), v.end(), Compare());
//		// 取前k个
//		vector<string> strV;
//		for (int i = 0; i < k; ++i)
//		{
//			strV.push_back(v[i].first);
//		}
//		return strV;
//	}
//};

int main()
{
	test06();
	return 0;
}
